#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

#define LENGTH 1000000
#define ITERAT 1000000
#define SLINESIZE 64
#define MAX_ASSOC 16
#define MAX_SET_NUM 8192
#define BANK_BIT_0 6
#define BANK_OFFSET 1
#define QUEUE_SIZE 512
#define MEM_BANK_NUM 16
#define HIT_MISS_NUM 2
#define CACHE_BANK_NUM 1


typedef unsigned long long LARGEINT;
static LARGEINT TOTAL_CYCLES = 0;
static const int core_num = 1;
static const int queue_length = 64;

static long int l2read = 1;
static long int l2write = 1;
static long int l2restore = 1;
static long int l1read = 1;
static long int l1write = 1;
static long int l2readhit = 1;
static long int l2writehit = 1;

static int restore_enable = 1;

#define ISSUE_WIDTH 4
static LARGEINT maxd[ISSUE_WIDTH] = {};
static int ooo_enable = 0;
static int outoforder = 0;

static int validate = 1;

typedef struct element {
	LARGEINT InsNum;
	char Ncc;
	LARGEINT Address;
	char Data[SLINESIZE];
	char Odata[SLINESIZE];
} element_t;

typedef enum {
	ACCESS_TYPE_LOAD,
	ACCESS_TYPE_STORE,
	ACCESS_TYPE_WRITEBACK
} ACCESS_TYPE;

typedef struct CACHE_SET_LRU_PO {
	LARGEINT _tags[MAX_ASSOC];
	int _repl[MAX_ASSOC];
	LARGEINT  _addr[MAX_ASSOC];
	bool _clean[MAX_ASSOC];
	char _data[MAX_ASSOC][SLINESIZE*2];
} SET_t;

typedef struct BANK {
	LARGEINT operation_start_cycle;
	int previous_latency;
	LARGEINT read_start_cycle;
	LARGEINT write_start_cycle;
	int read;
} BANK_t;

typedef struct MEMORY {
	int bank_num;
	BANK_t _bank[MEM_BANK_NUM];
	int read_latency;
	int reset_latency;
	int queue;
	int bankQueue[QUEUE_SIZE];
} MEM_t;

typedef struct CACHE {
	int _setNum;
	CACHE_SET_LRU_PO _sets[MAX_SET_NUM];
	CACHE* below;
	MEMORY* bottom;
	int read_latency;
	int tag_latency;
	int write_latency;
	int restore_latency;
	bool conflict;
	int _cacheId;
	int _cacheSize;
	int _lineSize;
	int _associativity;
	int _lineShift;
	int _setIndexMask;
	LARGEINT _access[HIT_MISS_NUM];
	BANK_t _bank[CACHE_BANK_NUM];
} CACHE_t;

bool IsPower2(int n) {
	return ((n & (n - 1)) == 0);
}

int FloorLog2(int n) {
	int p = 0;
	if (n == 0) return -1;
	if (n & 0xffff0000) {
		p += 16;
		n >>= 16;
	}
	if (n & 0x0000ff00) {
		p +=  8;
		n >>=  8;
	}
	if (n & 0x000000f0) {
		p +=  4;
		n >>=  4;
	}
	if (n & 0x0000000c) {
		p +=  2;
		n >>=  2;
	}
	if (n & 0x00000002) {
		p +=  1;
	}
	return p;
}

int CeilLog2(int n) {
	return FloorLog2(n - 1) + 1;
}

void SplitAddress(CACHE_t* cc, LARGEINT addr, LARGEINT* tag, int* setIndex) {
	*tag = addr >> cc->_lineShift;
	*setIndex = *tag & cc->_setIndexMask;
}

void d2b(char* st,  char tar) {
	for (int j = 0; j < 8; j++) {
		st[j] = 0;
	}
	int i = 0;
	unsigned char mtar = (unsigned char)tar;
	while (mtar > 0) {
		st[i] = mtar % 2;
		mtar = mtar / 2;
		i++;
	}
}

int gBankNum (LARGEINT addr, int bnum) {
	int bank = (addr >> BANK_BIT_0) & (bnum - 1);
	return bank;
}

int Find(SET_t * tar, LARGEINT tag, int assoc) {
	for (int way = 0; way < assoc; way++) {
		if(tar->_tags[way] == tag) {
			return way;
		}
	}
	return -1;
}

void Update(SET_t * tar, int way, int assoc) {
	assert(way < assoc);
	int currentp = tar->_repl[way];
	for(int i=0; i < assoc; i++) {
		if( tar->_repl[i] < currentp ) {
			tar->_repl[i] ++;
		}
	}
	tar->_repl[way] = 0;
}

int Replace(SET_t* tar, LARGEINT tag, int assoc) {
	int lruWay = 0;
	for (int way = 0; way < assoc; way++) {
		if(tar->_repl[way] == (assoc-1)) {
			lruWay = way;
			tar->_tags[lruWay] = tag;
			break;
		}
	}
	return lruWay;
}

int AccessSingleLine(MEM_t* mem, LARGEINT addr, ACCESS_TYPE accessType, char* new_data, char* old_data) {
	int penalty = 0;
	if(accessType == ACCESS_TYPE_LOAD) {
		int rp = 0;
		int bn = gBankNum(addr, mem->bank_num);
		for(int index = 0; index < core_num; index++) {
			int tbn = (bn + BANK_OFFSET * index) % mem->bank_num;
			LARGEINT lasttime = mem->_bank[tbn].previous_latency + mem->_bank[tbn].operation_start_cycle;
			if(TOTAL_CYCLES > lasttime) {
				mem->_bank[tbn].operation_start_cycle = TOTAL_CYCLES;
				mem->_bank[tbn].previous_latency = mem->read_latency;
				rp += mem->read_latency;
				mem->_bank[tbn].read = 1;
			} else {
				rp += (mem->read_latency + lasttime - TOTAL_CYCLES);
				mem->_bank[tbn].operation_start_cycle = lasttime;
				mem->_bank[tbn].previous_latency = mem->read_latency;
				mem->_bank[tbn].read = 1;
			}
		}
		penalty += (rp/core_num);
	}

	/*
	if(accessType == ACCESS_TYPE_STORE) {
		int latency = mem->reset_latency;
		int bn = gBankNum(addr, mem->bank_num);
		for(int index = 0; index < core_num; index++) {
			int tbn = (bn + BANK_OFFSET * index) % mem->bank_num;
			LARGEINT lasttime = mem->_bank[tbn].previous_latency + mem->_bank[tbn].operation_start_cycle;
			if(TOTAL_CYCLES > lasttime) {
				mem->_bank[tbn].operation_start_cycle = TOTAL_CYCLES;
				mem->_bank[tbn].previous_latency = latency;
				mem->_bank[tbn].read = 0;
			}else{
				int tt = mem->queue;
				mem->bankQueue[tt] = tbn;
				mem->queue ++;
			}
		}
	}

	if(mem->queue >= queue_length) {
		int latency = mem->reset_latency;
		for(int i = 0; i < queue_length; i++) {
			int bne = mem->bankQueue[i];
			LARGEINT lasttime = mem->_bank[bne].previous_latency + mem->_bank[bne].operation_start_cycle;
			if(TOTAL_CYCLES > lasttime) {
				mem->_bank[bne].operation_start_cycle = TOTAL_CYCLES;
				mem->_bank[bne].previous_latency = latency;
				mem->_bank[bne].read = 2;
			} else {
				mem->_bank[bne].operation_start_cycle = lasttime;
				mem->_bank[bne].previous_latency = latency;
				mem->_bank[bne].read = 2;
			}
		}
		mem->queue = 0;
	}
	*/

	return penalty;
}


int AccessSingleLine(CACHE_t* cc, LARGEINT addr, ACCESS_TYPE accessType, 
		char* ndata, char* odata, bool dirty, bool* upgo) {
	LARGEINT tag;
	int setIndex;
	int penalty = 0;
	SplitAddress(cc, addr, &tag, &setIndex);
	assert(setIndex < cc->_setNum);
	assert(setIndex >= 0);
	CACHE_SET_LRU_PO * set = &(cc->_sets[setIndex]);
	assert(set != NULL);
	long index = Find(set, tag, cc->_associativity);

	bool hit = true;
	penalty += cc->tag_latency;
	if(index == -1) hit = false;

	if (!hit) {
		int way = Replace(set, tag, cc->_associativity);
		bool clean = set->_clean[way];
		LARGEINT bAddr = set->_addr[way];



		bool ppp = true;

		//if(accessType != ACCESS_TYPE_WRITEBACK){
		if(cc->below != NULL){
			penalty += AccessSingleLine(cc->below, addr, ACCESS_TYPE_LOAD, ndata, odata, true, &ppp);
		}else{
			if(cc->bottom != NULL){
				penalty += AccessSingleLine(cc->bottom, addr, ACCESS_TYPE_LOAD, ndata, odata);
			}
		}
		//}








		bool ttt = true;

		if(cc->below != NULL) {
			clean = false;
			//if(clean == false || validate == true){
			if(clean == false) {
				penalty += AccessSingleLine(cc->below, bAddr, ACCESS_TYPE_WRITEBACK, 
						&set->_data[way][0], &set->_data[way][SLINESIZE], clean, &ttt);
			}
		} else {
			if(cc->bottom != NULL){
				if(clean == false) {
					penalty += AccessSingleLine(cc->bottom, bAddr, ACCESS_TYPE_STORE, 
							&set->_data[way][0], &set->_data[way][SLINESIZE]);
				}
			}
		}

/*
		bool ppp = true;

		//if(accessType != ACCESS_TYPE_WRITEBACK){
		if(cc->below != NULL){
			penalty += AccessSingleLine(cc->below, addr, ACCESS_TYPE_LOAD, ndata, odata, true, &ppp);
		}else{
			if(cc->bottom != NULL){
				penalty += AccessSingleLine(cc->bottom, addr, ACCESS_TYPE_LOAD, ndata, odata);
			}
		}
		//}

*/




		Update(set, way, cc->_associativity);
		set->_addr[way]= addr;

		if(accessType == ACCESS_TYPE_STORE) set->_clean[way] = false;
		if(accessType == ACCESS_TYPE_LOAD){
			if(cc->below == NULL && cc->bottom != NULL) 
				set->_clean[way] = true;
			else if(cc->below != NULL && cc->bottom == NULL)
				set->_clean[way] = ppp;
		}
		if(accessType == ACCESS_TYPE_WRITEBACK) set->_clean[way] = dirty;
		memcpy(&set->_data[way][0], ndata, SLINESIZE);
		memcpy(&set->_data[way][SLINESIZE], odata, SLINESIZE);
	
		if(cc->_cacheId == 1){
			if(accessType == ACCESS_TYPE_LOAD){
				l2read ++;
			}else{
				l2write ++;
			}
		}else{
			if(accessType == ACCESS_TYPE_LOAD) {
				l1read ++;
			}else{
				l1write ++;
			}
		}

		if(accessType != ACCESS_TYPE_LOAD){
			int myway = 0;
			LARGEINT lasttime = cc->_bank[myway].previous_latency + cc->_bank[myway].operation_start_cycle;
			if(TOTAL_CYCLES > lasttime) {
				cc->_bank[myway].operation_start_cycle = TOTAL_CYCLES;
				cc->_bank[myway].previous_latency = cc->write_latency;
				cc->_bank[myway].read = 0;
			} else {
				cc->_bank[myway].operation_start_cycle = lasttime;
				cc->_bank[myway].previous_latency = cc->write_latency;
				cc->_bank[myway].read = 0;
			}
		}
	} else {
		Update(set, index, cc->_associativity);

		if(accessType == ACCESS_TYPE_STORE) {
			memcpy(&set->_data[index][0], ndata, SLINESIZE);
			set->_clean[index] = false;
		}

		if(accessType == ACCESS_TYPE_WRITEBACK && dirty == false) {
			memcpy(&set->_data[index][0], ndata, SLINESIZE);
			memcpy(&set->_data[index][SLINESIZE], odata, SLINESIZE);
			set->_clean[index] = dirty;
		}
		
		if(accessType == ACCESS_TYPE_LOAD) {
			*upgo = set->_clean[index];
			if(cc->_cacheId == 1){
				l2read ++;
				l2readhit ++;
			}else{
				l1read ++;
			}
			int rp = 0;
			int myway = 0;
			LARGEINT lasttime = cc->_bank[myway].previous_latency + cc->_bank[myway].operation_start_cycle;
			if(TOTAL_CYCLES > lasttime) {
				cc->_bank[myway].operation_start_cycle = TOTAL_CYCLES;
				if(cc->_cacheId == 1){
					if(restore_enable){
						cc->_bank[myway].previous_latency = cc->read_latency + cc->restore_latency;
						l2restore ++;
					}else{
						cc->_bank[myway].previous_latency = cc->read_latency;
					}
				}else{
					cc->_bank[myway].previous_latency = cc->read_latency;
				}
				rp += cc->read_latency;
				cc->_bank[myway].read = 1;
			} else {
				rp += (cc->read_latency + lasttime - TOTAL_CYCLES);
				cc->_bank[myway].operation_start_cycle = lasttime;
				if(cc->_cacheId == 1){
					if(restore_enable){
						cc->_bank[myway].previous_latency = cc->read_latency + cc->restore_latency;
						l2restore ++;
					}else{
						cc->_bank[myway].previous_latency = cc->read_latency;
					}
				}else{
					cc->_bank[myway].previous_latency = cc->read_latency;
				}
				cc->_bank[myway].read = 1;
			}
			penalty += rp;
		}else{
			if((accessType == ACCESS_TYPE_WRITEBACK && dirty == false) || accessType == ACCESS_TYPE_STORE){
		//        if(accessType == ACCESS_TYPE_WRITEBACK || accessType == ACCESS_TYPE_STORE){
				if(cc->_cacheId == 1){
					l2write ++;
					l2writehit ++;
				}else{
					l1write ++;
				}
				int myway = 0;
				LARGEINT lasttime = cc->_bank[myway].previous_latency + cc->_bank[myway].operation_start_cycle;
				if(TOTAL_CYCLES > lasttime) {
					cc->_bank[myway].operation_start_cycle = TOTAL_CYCLES;
					cc->_bank[myway].previous_latency = cc->write_latency;
					cc->_bank[myway].read = 0;
				} else {
					cc->_bank[myway].operation_start_cycle = lasttime;
					cc->_bank[myway].previous_latency = cc->write_latency;
					cc->_bank[myway].read = 0;
				}
			}
		}
	}
	cc->_access[hit] ++;

	return penalty;
}

void initialMemory(MEMORY *mm, int bank_n, int read_l, int reset_l) {
	mm->bank_num = bank_n;
	mm->read_latency = read_l;
	mm->reset_latency = reset_l;
	mm->queue = 0;

	for(int i = 0; i < MEM_BANK_NUM; i++) {
		mm->_bank[i].operation_start_cycle = 0;
		mm->_bank[i].read_start_cycle = 0;
		mm->_bank[i].write_start_cycle = 0;
		mm->_bank[i].previous_latency = 0;
		mm->_bank[i].read = -1;
	}

	for(int i = 0; i < QUEUE_SIZE; i++) {
		mm->bankQueue[i] = 0;
	}
}

void initialCache(CACHE_t *mm, int cid, int cs, int ls, int so, int rl, int tl, int wl, int rel, CACHE_t* be, MEM_t* bm) {
	mm->read_latency = rl;
	mm->tag_latency = tl;
	mm->write_latency = wl;
	mm->restore_latency = rel;
	mm->conflict = true;
	mm->below = be;
	mm->bottom = bm;
	mm->_cacheId = cid;
	mm->_associativity = so;
	mm->_cacheSize = cs;
	mm->_lineSize = ls;
	mm->_lineShift = FloorLog2(mm->_lineSize);
	mm->_setIndexMask = (mm->_cacheSize / (mm->_associativity * mm->_lineSize)) - 1;
	mm->_setNum = mm->_setIndexMask + 1;

	assert(IsPower2(mm->_lineSize));
	assert(IsPower2(mm->_setIndexMask + 1));

	for(int i = 0; i < MAX_SET_NUM; i++) {
		for(int j = 0; j < MAX_ASSOC; j++) {
			mm->_sets[i]._tags[j] = 0;
			mm->_sets[i]._repl[j] = j;
			mm->_sets[i]._addr[j] = 0;
			mm->_sets[i]._clean[j] = false;
		}
	}

	for(int i = 0; i < CACHE_BANK_NUM; i++) {
		mm->_bank[i].operation_start_cycle = 0;
		mm->_bank[i].read_start_cycle = 0;
		mm->_bank[i].write_start_cycle = 0;
		mm->_bank[i].previous_latency = 0;
		mm->_bank[i].read = -1;
	}

	for(int i =0; i < HIT_MISS_NUM; i++) {
		mm->_access[i] = 0;
	}
}

void restoreCache(CACHE_t *l1, CACHE_t *l2, ifstream* inputFile) {
	inputFile->seekg(0, ios::beg);
	inputFile->read((char*)l1->_sets, sizeof(SET_t) * l1->_setNum);
	streamoff offset = sizeof(SET_t) * l1->_setNum;
	inputFile->seekg(offset, ios::beg);
	inputFile->read((char*)l2->_sets, sizeof(SET_t) * l2->_setNum);
	inputFile->close();
}


int main(int argc, char *argv[]) {
	ifstream filein0 (argv[1], ios::in|ios::binary);
	MEM_t* mm = (MEM_t *) malloc(sizeof(MEM_t));
	initialMemory(mm, 16, 200, 200);

	//read fast: 15 slow: 25
	//write 40
	//
	//fast 16 slow 32
	
	CACHE_t* L2 = (CACHE_t *)malloc(sizeof(CACHE_t));
	initialCache(L2, 1, 8388608, 64, 16, 32, 1, 48, 0, NULL, mm);
	//initialCache(L2, 1, 8388608, 64, 16, 20, 1, 40, 0, NULL, mm);
	CACHE_t* DL = (CACHE_t *)malloc(sizeof(CACHE_t));
	initialCache(DL, 0, 32768, 64, 4, 1, 0, 1, 0, L2, NULL);
	restoreCache(DL, L2, &filein0);

	LARGEINT dTOTAL_CYCLES = 0;
	LARGEINT dprevious = 0;
	TOTAL_CYCLES = 0;
	LARGEINT previous = 0;

	ifstream filein1 (argv[2], ios::in|ios::binary);

	streamoff offset = 0;
	if (filein1.is_open()) {
		element_t* sample = (element_t *) malloc(sizeof(element_t) * LENGTH);
		filein1.seekg(offset, ios::beg);
		filein1.read((char*)sample, sizeof(element_t) * LENGTH);
		dTOTAL_CYCLES = sample[0].InsNum;
		dprevious = sample[0].InsNum;

		for(int j = 0; j < LENGTH; j++) {
			TOTAL_CYCLES += (sample[j].InsNum - previous) / ISSUE_WIDTH;
			previous = sample[j].InsNum;
			bool gogo = true; 
			if(sample[j].Ncc) {
				if(ooo_enable == 1) {
					maxd[outoforder] = AccessSingleLine(DL, sample[j].Address, 
							ACCESS_TYPE_LOAD, sample[j].Data, sample[j].Odata, true, &gogo);
					if(outoforder == (ISSUE_WIDTH - 1)){
						outoforder = 0;
						LARGEINT mmm = 0;
						for(int oo = 0; oo < (ISSUE_WIDTH - 1); oo++){
							if(maxd[oo] > mmm)
								mmm = maxd[oo];
						}
						TOTAL_CYCLES += mmm;
					}else{
						outoforder ++;
					}
				}else{
					TOTAL_CYCLES += AccessSingleLine(DL, sample[j].Address, 
							ACCESS_TYPE_LOAD, sample[j].Data, sample[j].Odata, true, &gogo);
				}
			} else {
				TOTAL_CYCLES += AccessSingleLine(DL, sample[j].Address, 
						ACCESS_TYPE_STORE, sample[j].Data, sample[j].Odata, false, &gogo);
			}
		}

		cout << "cycles: " << (TOTAL_CYCLES - dTOTAL_CYCLES) << endl;
		cout << "ins #: " << previous - dprevious << endl;
		cout << "CPI: " << (TOTAL_CYCLES - dTOTAL_CYCLES) / (double) (previous - dprevious) << endl;
		cout << "L1 Hit: " << DL->_access[true] / (double) (DL->_access[true] + DL->_access[false]) 
			<< " " << (DL->_access[true] + DL->_access[false]) << endl;
		cout << "L2 Hit: " << L2->_access[true] / (double) (L2->_access[true] + L2->_access[false]) 
			<< " " << (L2->_access[true] + L2->_access[false]) << endl;

		cout << "L2 read: " << l2read << endl;
		cout << "L2 write: " << l2write << endl;
		cout << "L2 restore: " << l2restore << endl;
		cout << "L1 read: " << l1read << endl;
		cout << "L1 write: " << l1write << endl;
		cout << "L2 read hit: " << l2readhit << endl;
		cout << "L2 write hit: " << l2writehit << endl;

		dTOTAL_CYCLES = TOTAL_CYCLES;
		dprevious = previous;
		DL->_access[true] = 0;
		DL->_access[false] = 0;
		L2->_access[true] = 0;
		L2->_access[false] = 0;

		filein1.close();
		free(sample);
	}

	free(DL);
	free(L2);
	free(mm);
	return 0;
}
